package lc;
import java.util.*;


import org.junit.*;
public class Ex460 {
    class LFUCache1 {

        class Node {
            int key, val;
            Node prev, next;
    
            public Node (int key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        //实际上，每个Bucket中的所有key放在一起，都是不一样的，就好像1.7的HashMap，
        //Bucket[]本身是一个table,而每个Bucket就是一个Segment
        //而既然整体是一个Hash表，当然key全部不一样
        class Bucket {
            Node head, tail;
            Bucket left, right; //Bucket表也是一个双向链表
            int idx; //idx == 该位置元素的次数
            Map<Integer, Node> map; //记录了key和LRU链表的映射
            //[一个LRU链表(Bucket)只记录一种次数的key（意思是这些key的访问次数相同），
            //单纯为了保证使用了就能前移的性质]

            public Bucket(int idx) {
                this.idx = idx;
                map = new HashMap<>();
                head = new Node(-1,-1); //dommy头尾节点
                tail = new Node(-1,-1); //dommy节点的存在使得本算法不需要考虑头尾元素
                head.next = tail;
                tail.prev = head;
            }

            public void put(int key, int val)  {
                Node node;
                if (map.containsKey(key)) {
                    node = map.get(key);
                    node.val = val;
                    //将其从中间移除，并在后面统一前移
                    node.prev.next = node.next;
                    node.next.prev = node.prev;
                } else {
                    node = new Node(key, val);
                    map.put(key, node);
                }

                //将node添加到首位
                node.next = head.next;
                node.prev = head;
                head.next.prev = node;
                head.next = node;
            }

            //删除一个Bucket中的key
            public Node remove(int key) {
                if (map.containsKey(key)) {
                    Node node = map.get(key);
                    node.prev.next = node.next;
                    node.next.prev = node.prev;
                    map.remove(key);
                    return node;
                }
                return null;
            }

            //当达到capacity后，删除末尾元素
            public Node removeLast() {
                Node node = tail.prev;
                return remove(node.key);
            }

            public boolean isEmpty() {
                return head.next == tail;
            }
        }


        Map<Integer, Bucket> buckets;//key与对应桶位的映射：key与桶位是多对一的关系
        Bucket head,tail; //bucket[]本身也是双向链表，使用dommy
        int capacity; //容量
        int size; //当前拥有的k-v数量，不能大于capacity

        public LFUCache1(int capacity) {
            buckets = new HashMap<>();
            head = new Bucket(-1);
            tail = new Bucket(-1);
            head.right = tail;
            tail.left = head;
            size = 0;
            this.capacity = capacity;
        }

        //将得到的那个key对应的node从左边的bucket移动到idx比他大一个bucket
        public int get(int key) {
            if (buckets.containsKey(key)) {
                Bucket from = buckets.get(key), to = null;
                if (from.right.idx != from.idx + 1) {
                    //不存在比当前大一个idx的桶位
                    to = new Bucket(from.idx + 1);
                    //插到当前桶位的右边
                    to.right = from.right;
                    to.left = from;
                    from.right.left = to;
                    from.right = to;
                } else {
                    to = from.right;
                }

                //将这个节点从from桶移除，添加到to桶
                Node node = from.remove(key);
                to.put(node.key, node.val);

                //更新桶位信息
                buckets.put(key, to);

                //删除空桶位
                deleteIfEmpty(from);
                return node.val;
            }
            return -1;
        }


        public void put(int key, int value) {
            if (this.capacity == 0) return; //存在0容量的用例
            if (buckets.containsKey(key)) { 
                Bucket from = buckets.get(key);
                from.put(key, value); //修改bucket内部node的值

                //访问次数加一，可以利用get来进行移动
                this.get(key);
            } else {
                //整个Bucket[]都没有这个key，需要添加一个key
                if (size == capacity) {
                    //已经满了，删除最小访问次数的最早访问的点
                    Bucket first = head.right;
                    Node remove = first.removeLast();
                    buckets.remove(remove.key);
                    size--;//后面可以统一加上去

                    //删除空桶位
                    deleteIfEmpty(first);
                }

                //由于不存在这个key，就说明添加这个k-v的节点后，必然会添加到idx==1的桶位
                Bucket first;
                if ((first = head.right).idx != 1) {
                    //不存在一号桶就创建一号桶位
                    first = new Bucket(1);
                    first.left = head;
                    first.right = head.right;
                    head.right = first;
                    first.right.left = first;
                }

                //将这个k-v添加到一号桶
                first.put(key, value);
                buckets.put(key, first);
                size++;
            }
        }
                
        private void deleteIfEmpty(Bucket bucket) {
            if (bucket.isEmpty()) {
                bucket.left.right = bucket.right;
                bucket.right.left = bucket.left;
            }
        }
    }

    @Test
    public void test2() {
        LFUCache lru = new LFUCache(3);
        lru.put(2, 2);
        lru.put(1, 1);
        // lru.get(1);
        int val = lru.get(2);
        System.out.println(val);
        System.out.println(lru.get(1));
        System.out.println(lru.get(2));

        /*  */
        lru.put(3, 3);
        lru.put(4, 4);
        System.out.println(lru.get(3));
    }

    @Test
    public void test() {
        LFUCache lru = new LFUCache(2);
        lru.put(1, 1);
        lru.put(2, 2);
        // lru.get(1);
        System.out.println(lru.get(1));
        lru.put(3, 3);
        System.out.println(lru.get(2));
        System.out.println(lru.get(3));
        lru.put(4, 4);
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */



     //仿照1.7的HashMap，使用双重链表的方式来存储LFU
     //不同点在于：这里的外部存储由自身被访问的次数决定
     //每被访问一次，该Node从这个次数的Segment取出，放到次数+1的Segment中
     //
     //Segment为了有LRU的感觉，仿照LRU进行设计
    class LFUCache {

        class Node {
            Node left, right;
            int key, value;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        class Segment {
            //Segment自身也是一个双向链表，仿照跳表的链表进行有序
            Segment left, right;
            Node tail, head; //执行LRU缓存
            int times;
            int size;
            Map<Integer, Node> map;

            public Segment(int times) {
                head = tail = new Node(-1, -1);
                this.times = times;
                map = new HashMap<>();
                this.size = 0;
                head.right = tail;
                tail.left = head;
            }

            public void insertToHead(Node node) {
                node.right = head.right;
                node.left = head;
                head.right.left = node;
                head.right = node;
                map.put(node.key, node);
                size++;
            }

            public void remove(Node node) {
                node.left.right = node.right;
                node.right.left = node.left;
                map.remove(node.key);
                size--;
            }

            public Node getValue(int key) {
                Node node = map.get(key);
                remove(node);
                Segment next = this.right;
                if (next.times != this.times + 1) {
                    //还没这个times的桶位
                    next = new Segment(times + 1);
                    next.right = this.right;
                    next.left = this;
                    this.right.left = next;
                    this.right = next;
                }
                //插到next的桶位中
                next.insertToHead(node);
                deleteIfEmpty();
                return node;
            }

            public void deleteIfEmpty() {
                if (this.size == 0) {
                    this.left.right = this.right;
                    this.right.left = this.left;
                }
            }

            public void removeToFirst(Node node) {
                node = tail.left;
                remove(node);
                insertToHead(node);
            }

            public void removeLast() {
                remove(tail.left);
                deleteIfEmpty();
            }
        }

        //记录当前key在哪个桶位中
        Map<Integer, Segment> idx;
        int size, capacity;
        Segment head, tail;

        // public void insert

        public LFUCache(int capacity) {
            idx = new HashMap<>();
            size = 0;
            head = tail = new Segment(0); //首位为0次
            head.right = tail;
            tail.left = head;
            this.capacity = capacity;
        }

        public void removeOldest() {
            Segment first = head.right;
            first.removeLast();
        }
        
        public void toNext(Segment segment, int key) {
            idx.put(key, idx.get(key).right);
        }

        public int get(int key) {
            if (!idx.containsKey(key)) {
                return -1;
            } else {
                Segment segment = idx.get(key);
                toNext(segment, key);
                return segment.getValue(key).value;
            }
        }
        
        public void put(int key, int value) {
            if (!idx.containsKey(key)) {
                if (this.size == capacity) {
                    removeOldest();
                }
                Segment next = head.right;
                if (next.times != 1) {
                    next = new Segment(1);
                    next.right = head.right;
                    next.left = head;
                    head.right.left = next;
                    head.right = next;
                }
                idx.put(key, next);
                next.insertToHead(new Node(key, value));
                this.size++;
            } else {
                Segment segment = idx.get(key);
                Node node = segment.getValue(key);
                toNext(segment, key);
                node.value = value;
            }
        }
    }
}
